package puzzle.projecteuler.p200;

import java.util.Arrays;

import astudy.util.AdvMath;

public class Problem183 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		int[] ms = new int[3700];
		ms[0] = 0;
		for (int i = 1; i < ms.length; i ++) {
			ms[i] = (int)Math.floor(Math.pow(1+1.0/i, i)*(i+1));
		}
		long sum = 0;
		for (int i = 5; i <= 10000; i ++) {
			int k = Arrays.binarySearch(ms, i);
			int x = 0;
			if ( k < 0) {
				x = -k-1;
			} else {
				x = k;
			}
			//check
			int d = (int)AdvMath.gcd(i, x);
			x = x/d;
			while (x%2 == 0) x/=2;
			while (x%5 == 0) x/=5;
			if (x == 1) {
				sum -= i;
			} else {
				sum += i;
			}
		}
		System.out.println(sum);
	}
}
